//https://leetcode.cn/problems/distant-barcodes/
//class Solution {
//public:
//    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
//        // 在一个仓库里 有一排条形码 其中第i个条形码为 barcodes[i];
//        // 先处理次数最多的;
//        // hash表统计每个数出现的频次;
//        std::unordered_map<int, int> hash;
//        int maxVal = 0;
//        int maxCount = 0;
//        for (auto x : barcodes) {
//            if (maxCount < ++hash[x]) {
//                maxCount = hash[x];
//                maxVal = x;
//            }
//        }
//        int n = barcodes.size();
//        std::vector<int> ret(n);
//        int index = 0;
//        for (int i = 0; i < maxCount; i++) {
//            ret[index] = maxVal;
//            index += 2;
//        }
//        hash.erase(maxVal);
//        for (const auto& [x, y] : hash) {
//            for (int i = 0; i < y; i++) {
//                if (index >= n) {
//                    index = 1;
//                }
//                ret[index] = x;
//                index += 2;
//            }
//        }
//        return ret;
//    }
//};
//
//
//
//https://leetcode.cn/problems/russian-doll-envelopes/
//class Solution {
//public:
//    int maxEnvelopes(vector<vector<int>>& envelopes) {
//        sort(envelopes.begin(), envelopes.end(),
//            [&](const vector<int>& v1, const vector<int>& v2) {
//                return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
//            });
//        vector<int> ret;
//        ret.push_back(envelopes[0][1]);
//        for (int i = 1; i < envelopes.size(); i++) {
//            int nextsecondvalue = envelopes[i][1];
//            if (nextsecondvalue > ret.back()) {
//                ret.push_back(nextsecondvalue);
//            }
//            else {
//                int left = 0;
//                int right = ret.size() - 1;
//                while (left < right) {
//                    int mid = (left + right) / 2;
//                    if (ret[mid] >= nextsecondvalue) {
//                        right = mid;
//                    }
//                    else {
//                        left = mid + 1;
//                    }
//                }
//                ret[left] = nextsecondvalue;
//            }
//        }
//        return ret.size();
//    }
//};
//
//
//
//https://leetcode.cn/problems/greatest-sum-divisible-by-three/
//class Solution {
//public:
//    int maxSumDivThree(vector<int>& nums) {
//        const int INF = 0x3f3f3f3f;
//        int sum = 0;
//        int x1 = INF, x2 = INF, y1 = INF, y2 = INF;
//        for (const auto x : nums) {
//            sum += x;
//            if (x % 3 == 1) {
//                if (x < x1) {
//                    x2 = x1, x1 = x;
//                }
//                else if (x < x2) {
//                    x2 = x;
//                }
//            }
//            else if (x % 3 == 2) {
//                if (x < y1) {
//                    y2 = y1, y1 = x;
//                }
//                else if (x < y2) {
//                    y2 = x;
//                }
//            }
//        }
//        if (sum % 3 == 0) {
//            return sum;
//        }
//        else if (sum % 3 == 1) {
//            return max(sum - x1, sum - y1 - y2);
//        }
//        else {
//            return max(sum - y1, sum - x1 - x2);
//        }
//    }
//};
//
//https://leetcode.cn/problems/reorganize-string/
//class Solution {
//public:
//    string reorganizeString(string s) {
//         s 只包含小写字母;
//        int hash[26] = { 0 };
//        char maxChar = ' ';
//        int maxCount = 0;
//        for (auto ch : s) {
//            if (maxCount < ++hash[ch - 'a']) {
//                maxChar = ch;
//                maxCount = hash[ch - 'a'];
//            }
//        }
//        int n = s.size();
//        if (maxCount > (n + 1) / 2) {
//            return "";
//        }
//        string ret(n, ' ');
//        int index = 0;
//         先处理出现次数最多的那个字符;
//        for (int i = 0; i < maxCount; i++) {
//            ret[index] = maxChar;
//            index += 2;
//        }
//        hash[maxChar - 'a'] = 0;
//        for (int i = 0; i < 26; i++) {
//            for (int j = 0; j < hash[i]; j++) {
//                if (index >= n) {
//                    index = 1;
//                }
//                ret[index] = 'a' + i;
//                index += 2;
//            }
//        }
//        return ret;
//    }
//};